//
//  00_反转链表.swift
//  LeetCode
//
//  Created by Hao on 2020/6/21.
//  Copyright © 2020 Hao. All rights reserved.
//

import Foundation

struct ReversalList {
    
    /// 使用递归方式反转链表
    /// - Parameter headNode: 头节点
    static func recursive<E>(linkedList headNode: LinkedNode<E>?) -> LinkedNode<E>? {
        if headNode == nil || headNode?.next == nil {
            return headNode
        }
        
        let newHead = recursive(linkedList: headNode?.next)
        headNode?.next?.next = headNode
        headNode?.next = nil
        
        return newHead
    }
    
    /// 使用while循环翻转
    static func loop<E>(linkedList headNode: LinkedNode<E>?) -> LinkedNode<E>? {
        if headNode == nil || headNode?.next == nil {
            return headNode
        }
        
        // 保存上次反转的头节点
        var previousHead: LinkedNode<E>? = nil
        var idxHead = headNode // 1
        
        while idxHead != nil {
            // 保存2, 本来 1->2
            let tmpNode = idxHead?.next
            
            // 翻转 2->1
            idxHead?.next = previousHead
            
            // 保存新的头节点
            previousHead = idxHead
            print(String(describing: previousHead))
            
            idxHead = tmpNode
        }
        
        return previousHead
    }
    
}

